// 时间复杂度: 平均O(nlog2n) 最坏O(nlog2n) 最好O(nlog2n)
// 空间复杂度: O(n)
// 稳定性: 稳定排序

class MergerSort {
private:
    static void mergerArray(int *array, int left, int right) {
        int temp[right - left + 1];
        int count = 0;
        int middle = (left + right) / 2;
        int i = left;
        int j = middle + 1;

        while (i <= middle && j <= right) {
            if (array[i] <= array[j]) {
                temp[count++] = array[i++];

            } else {
                temp[count++] = array[j++];
            }
        }

        while (i <= middle) temp[count++] = array[i++];
        while (j <= right) temp[count++] = array[j++];

        for (int k = left; k <= right; ++k) {
            array[k] = temp[k - left];
        }
    }

public:
    static void mergerSort(int *array, int left, int right) {
        if (right <= left) {
            return;
        }

        int middle = (left + right) / 2;

        mergerSort(array, left, middle);
        mergerSort(array, middle + 1, right);

        mergerArray(array, left, right);
    }
};